{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Word Ladder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: ladderLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词接龙"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>字典&nbsp;<code>wordList</code> 中从单词 <code>beginWord</code><em>&nbsp;</em>和 <code>endWord</code> 的 <strong>转换序列 </strong>是一个按下述规格形成的序列<meta charset=\"UTF-8\" />&nbsp;<code>beginWord -&gt; s<sub>1</sub>&nbsp;-&gt; s<sub>2</sub>&nbsp;-&gt; ... -&gt; s<sub>k</sub></code>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每一对相邻的单词只差一个字母。</li>\n",
    "\t<li><meta charset=\"UTF-8\" />&nbsp;对于&nbsp;<code>1 &lt;= i &lt;= k</code>&nbsp;时，每个<meta charset=\"UTF-8\" />&nbsp;<code>s<sub>i</sub></code>&nbsp;都在<meta charset=\"UTF-8\" />&nbsp;<code>wordList</code>&nbsp;中。注意， <code>beginWord</code><em>&nbsp;</em>不需要在<meta charset=\"UTF-8\" />&nbsp;<code>wordList</code>&nbsp;中。<meta charset=\"UTF-8\" /></li>\n",
    "\t<li><code>s<sub>k</sub>&nbsp;== endWord</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>给你两个单词<em> </em><code>beginWord</code><em>&nbsp;</em>和 <code>endWord</code> 和一个字典 <code>wordList</code> ，返回 <em>从&nbsp;<code>beginWord</code> 到&nbsp;<code>endWord</code> 的 <strong>最短转换序列</strong> 中的 <strong>单词数目</strong></em> 。如果不存在这样的转换序列，返回 <code>0</code> 。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>beginWord = \"hit\", endWord = \"cog\", wordList = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>一个最短转换序列是 \"hit\" -&gt; \"hot\" -&gt; \"dot\" -&gt; \"dog\" -&gt; \"cog\", 返回它的长度 5。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>beginWord = \"hit\", endWord = \"cog\", wordList = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\"]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>endWord \"cog\" 不在字典中，所以无法进行转换。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= beginWord.length &lt;= 10</code></li>\n",
    "\t<li><code>endWord.length == beginWord.length</code></li>\n",
    "\t<li><code>1 &lt;= wordList.length &lt;= 5000</code></li>\n",
    "\t<li><code>wordList[i].length == beginWord.length</code></li>\n",
    "\t<li><code>beginWord</code>、<code>endWord</code> 和 <code>wordList[i]</code> 由小写英文字母组成</li>\n",
    "\t<li><code>beginWord != endWord</code></li>\n",
    "\t<li><code>wordList</code> 中的所有字符串 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [word-ladder](https://leetcode.cn/problems/word-ladder/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [word-ladder](https://leetcode.cn/problems/word-ladder/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"hit\"\\n\"cog\"\\n[\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]', '\"hit\"\\n\"cog\"\\n[\"hot\",\"dot\",\"dog\",\"lot\",\"log\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        wordSet = set(wordList)\n",
    "        ret = 0\n",
    "        path_map = {beginWord:1}\n",
    "        queue = deque()\n",
    "        queue.append(beginWord)\n",
    "        if endWord in wordList:\n",
    "            while queue:\n",
    "                cur_word = queue.popleft()\n",
    "                path = path_map[cur_word]\n",
    "                for i in range(len(beginWord)):\n",
    "                    for j in range(26):\n",
    "                        new_word_list = list(cur_word)\n",
    "                        new_word_list[i] = chr(ord('a')+j)\n",
    "                        new_word = ''.join(new_word_list)\n",
    "                        if new_word == endWord:\n",
    "                            return path + 1\n",
    "                        if new_word in wordSet and new_word not in path_map:\n",
    "                            path_map[new_word] = path + 1\n",
    "                            queue.append(new_word)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        if beginWord in wordList:\n",
    "            wordList.remove(beginWord)\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        min_path = 1\n",
    "        middle_link_list = [endWord]\n",
    "        while len(middle_link_list) > 0:\n",
    "            middle_link_list_tmp = []\n",
    "            for j in middle_link_list:\n",
    "                wordList.remove(j)\n",
    "            for middle_link_word in middle_link_list:\n",
    "                difference_num = 0\n",
    "                for k in range(len(middle_link_word)):\n",
    "                    if beginWord[k] != middle_link_word[k]:\n",
    "                        difference_num += 1\n",
    "                if difference_num == 1:\n",
    "                    min_path += 1\n",
    "                    return min_path\n",
    "                else:\n",
    "                    for i in self.findSimilarWord(middle_link_word, wordList):\n",
    "                        if i not in middle_link_list_tmp:\n",
    "                            middle_link_list_tmp.append(i)\n",
    "            if len(middle_link_list_tmp) == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                middle_link_list = middle_link_list_tmp\n",
    "                min_path += 1\n",
    "    def findSimilarWord(self, word, wordlist):\n",
    "        middle_wordList = []\n",
    "        for each_word in wordlist:\n",
    "            difference_num = 0\n",
    "            for i in range(len(each_word)):\n",
    "                if word[i] != each_word[i]:\n",
    "                    difference_num += 1\n",
    "            if difference_num == 1:\n",
    "                middle_wordList.append(each_word)\n",
    "        return middle_wordList\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        \"\"\"\n",
    "        :type beginWord: str\n",
    "        :type endWord: str\n",
    "        :type wordList: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        wordset = set(wordList)\n",
    "        if endWord not in wordset:\n",
    "            return 0\n",
    "        res = 1\n",
    "        left,right = set(),set()\n",
    "        left.add(beginWord)\n",
    "        right.add(endWord)\n",
    "        while left or right:\n",
    "            newset = set()\n",
    "            left,right = right,left\n",
    "            for word in left:\n",
    "                for i in range(len(word)):\n",
    "                    for j in range(0, 26):\n",
    "                        newword = word[0:i]+chr(j+97)+word[i+1:]\n",
    "                        if newword in wordset:\n",
    "                            newset.add(newword)\n",
    "                            wordset.remove(newword)\n",
    "                        if newword in right:\n",
    "                            return res+1\n",
    "            res += 1\n",
    "            left = newset\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        \"\"\"\n",
    "        :type beginWord: str\n",
    "        :type endWord: str\n",
    "        :type wordList: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        wordset = set(wordList)\n",
    "        if endWord not in wordset:\n",
    "            return 0\n",
    "        res = 1\n",
    "        left,right = set(),set()\n",
    "        left.add(beginWord)\n",
    "        right.add(endWord)\n",
    "        while left or right:\n",
    "            newset = set()\n",
    "            left,right = right,left\n",
    "            for word in left:\n",
    "                for i in range(len(word)):\n",
    "                    for j in range(0, 26):\n",
    "                        newword = word[0:i]+chr(j+97)+word[i+1:]\n",
    "                        if newword in wordset:\n",
    "                            newset.add(newword)\n",
    "                            wordset.remove(newword)\n",
    "                        if newword in right:\n",
    "                            return res+1\n",
    "            res += 1\n",
    "            left = newset\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        \"\"\"\n",
    "        :type beginWord: str\n",
    "        :type endWord: str\n",
    "        :type wordList: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        wordset = set(wordList)\n",
    "        if beginWord in wordset:\n",
    "            wordset.remove(beginWord)\n",
    "        # 如果结束单词没有在给定单词数组中，直接返回\n",
    "        if endWord not in wordset:\n",
    "            return 0\n",
    "        res, curlevel, nextlevel, queue = 1, 1, 0, deque()\n",
    "        queue.append(beginWord)\n",
    "        while queue:\n",
    "            for _ in range(curlevel):\n",
    "                word = queue.popleft()\n",
    "                for i in range(len(word)):\n",
    "                    for j in range(0, 26):\n",
    "                        newword = word[0:i]+chr(j+97)+word[i+1:]\n",
    "                        if chr(j+97) != word[i]:\n",
    "                            if newword in wordset:\n",
    "                                nextlevel += 1\n",
    "                                queue.append(newword)\n",
    "                                wordset.remove(newword)\n",
    "                            if newword == endWord:\n",
    "                                return res+1\n",
    "            res += 1\n",
    "            curlevel = nextlevel\n",
    "            nextlevel = 0\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "from string import ascii_lowercase\n",
    "class Solution:\n",
    "    def ladderLength(self, begin, end, word):\n",
    "        \"\"\"\n",
    "        :type beginWord: str\n",
    "        :type endWord: str\n",
    "        :type wordList: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if end not in word : return 0\n",
    "        res = 0\n",
    "        q = Queue()\n",
    "        q.put(begin)\n",
    "        pword = set(word)\n",
    "        while q.empty() is not True:\n",
    "            for i in range(q.qsize()):\n",
    "                wd = q.get()\n",
    "                if wd == end : return res + 1\n",
    "                k =  { wd[:j] + p + wd [j+1:] for p in ascii_lowercase for j in range(len(wd))}\n",
    "                c = pword & k\n",
    "                pword = pword - c    \n",
    "                for j in c:\n",
    "                    q.put(j)\n",
    "            res += 1\n",
    "        return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        \"\"\"\n",
    "        :type beginWord: str\n",
    "        :type endWord: str\n",
    "        :type wordList: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        distance, stack, visited, loopup = 0, [beginWord], set([beginWord]), set(wordList)\n",
    "        while stack:\n",
    "            next_stack = []\n",
    "            for word in stack:\n",
    "                if word == endWord:\n",
    "                    return distance+1\n",
    "                for i in range(len(word)):\n",
    "                    for char in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                        trans_word = word[:i]+char+word[i+1:]\n",
    "                        if trans_word not in visited and trans_word in loopup:\n",
    "                            next_stack.append(trans_word)\n",
    "                            visited.add(trans_word)\n",
    "\n",
    "            distance += 1\n",
    "            stack = next_stack\n",
    "        return 0\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        \"\"\"\n",
    "        :type beginWord: str\n",
    "        :type endWord: str\n",
    "        :type wordList: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def valid(w1, w2):\n",
    "            count = 0\n",
    "            for i in range(len(w1)):\n",
    "                if w1[i] != w2[i]:\n",
    "                    count += 1\n",
    "                    if count > 1:\n",
    "                        return False\n",
    "            return count == 1\n",
    "        l = len(wordList)\n",
    "        graph = [[] for i in range(l+1)]\n",
    "        for i in range(l):\n",
    "            if valid(beginWord, wordList[i]):\n",
    "                graph[0].append(i+1)\n",
    "            for j in range(i+1,l):\n",
    "                if valid(wordList[i],wordList[j]):\n",
    "                    graph[i+1].append(j+1)\n",
    "                    graph[j+1].append(i+1)\n",
    "        queue = []\n",
    "        queue.append(0)\n",
    "        size = 1\n",
    "        res = 1\n",
    "        vis = [False for i in range(l+1)]\n",
    "        vis[0] = True\n",
    "        while len(queue) > 0:\n",
    "            temp = 0\n",
    "            for i in range(size):\n",
    "                index = queue.pop(0)\n",
    "                if index > 0  and wordList[index-1] == endWord:\n",
    "                    return res\n",
    "                for child in graph[index]:\n",
    "                    if not vis[child]:\n",
    "                        vis[child] = True\n",
    "                        queue.append(child)\n",
    "                        temp += 1\n",
    "            size = temp\n",
    "            res += 1\n",
    "        return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        \"\"\"\n",
    "        :type beginWord: str\n",
    "        :type endWord: str\n",
    "        :type wordList: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        wordSet = set(wordList)\n",
    "        step = 1\n",
    "        c = [chr(ord('a')+i) for i in range(26)]\n",
    "        queue = collections.deque()\n",
    "        queue.append(beginWord)\n",
    "        visited = set([beginWord])\n",
    "        N = len(beginWord)\n",
    "        while queue:\n",
    "            step += 1\n",
    "            length = len(queue)\n",
    "            for i in range(length):\n",
    "                word = queue.popleft()\n",
    "                for j in range(N):\n",
    "                    for s in c:\n",
    "                        newword = [w for w in word]\n",
    "                        newword[j] = s\n",
    "                        newword = ''.join(newword)\n",
    "                        if newword == endWord:\n",
    "                            return step\n",
    "                        elif newword in wordSet and newword not in visited:\n",
    "                            queue.append(newword)\n",
    "                            visited.add(newword)\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        \"\"\"\n",
    "        :type beginWord: str\n",
    "        :type endWord: str\n",
    "        :type wordList: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        if beginWord in wordList:\n",
    "            wordList.remove(beginWord)\n",
    "        wordDict = dict()\n",
    "        for word in wordList:\n",
    "            for i in range(len(word)):\n",
    "                tmp = word[:i] + \"_\" + word[i+1:]\n",
    "                wordDict[tmp] = wordDict.get(tmp, []) + [word]\n",
    "        \n",
    "        stack, visited = [(beginWord, 1)], set()\n",
    "        while stack:\n",
    "            word, step = stack.pop(0)\n",
    "            if word not in visited:\n",
    "                visited.add(word)\n",
    "                if word == endWord:\n",
    "                    return step\n",
    "                for i in range(len(word)):\n",
    "                    tmp = word[:i] + \"_\" + word[i+1:]\n",
    "                    neigh_words = wordDict.get(tmp, [])\n",
    "                    for neigh in neigh_words:\n",
    "                        if neigh not in visited:\n",
    "                            stack.append((neigh, step + 1))\n",
    "\n",
    "        return 0 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        \"\"\"\n",
    "        :type beginWord: str\n",
    "        :type endWord: str\n",
    "        :type wordList: List[str]\n",
    "        :rtype: int\n",
    "        边界：只有一个字符，有2个字符，endword不在list中\n",
    "        \"\"\"\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        link = self.setLink(wordList)\n",
    "        \n",
    "        queue = [(endWord,1)]\n",
    "        # dist = {endWord:1}\n",
    "        stepedL = set()\n",
    "        while len(queue)>0:\n",
    "            word,step = queue.pop(0)\n",
    "            # step = dist[word]\n",
    "            if word in stepedL:\n",
    "                continue\n",
    "            if self.diffLen(beginWord, word) == 1:\n",
    "                return step+1\n",
    "            stepedL.add(word)\n",
    "            for x in link[word]:\n",
    "                # if x not in stepedL:\n",
    "                queue.append((x,step+1))\n",
    "                    # dist[x] = step+1\n",
    "        return 0\n",
    "            \n",
    "    def setLink(self, wordList):\n",
    "        link = {x:set() for x in wordList}\n",
    "        for i in range(len(wordList)):\n",
    "            for j in range(i+1, len(wordList)):\n",
    "                if self.diffLen(wordList[i], wordList[j])==1:\n",
    "                    link[wordList[i]].add(wordList[j])\n",
    "                    link[wordList[j]].add(wordList[i])\n",
    "        return link\n",
    "    \n",
    "\n",
    "    def diffLen(self, w1, w2):\n",
    "        diff = 0\n",
    "        for i in range(len(w1)):\n",
    "            diff += 0 if w1[i]==w2[i] else 1\n",
    "        return diff\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        \"\"\"\n",
    "        :type beginWord: str\n",
    "        :type endWord: str\n",
    "        :type wordList: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(beginWord)\n",
    "        if endWord not in wordList or not wordList:\n",
    "            return 0\n",
    "        bfs = [beginWord]\n",
    "        need = {beginWord : 1}\n",
    "        for x in bfs:\n",
    "            if endWord in need:\n",
    "                return need[endWord]\n",
    "            for j in range(len(wordList) - 1, -1, -1):\n",
    "                i = 0\n",
    "                while i < l:\n",
    "                    if x[i] == wordList[j][i]:\n",
    "                        i += 1\n",
    "                        continue\n",
    "                    else:\n",
    "                        if x[i+1:] == wordList[j][i+1:] or i == l - 1:\n",
    "                            word = wordList.pop(j)\n",
    "                            bfs.append(word)\n",
    "                            need[word] = need[x] + 1\n",
    "                        break\n",
    "        return 0\n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList: return 0\n",
    "        cnt, n, words, = 1, len(beginWord), set(wordList)\n",
    "        bq, eq, nq = set([beginWord]), set([endWord]), set()\n",
    "        while bq:\n",
    "            for word in bq:\n",
    "                for new_word in [word[:i] + c + word[i + 1:] for i in range(n) for c in string.ascii_lowercase]:\n",
    "                    if new_word in eq:\n",
    "                        return cnt + 1\n",
    "                    if new_word in words:\n",
    "                        words.remove(new_word)\n",
    "                        nq.add(new_word)\n",
    "            cnt += 1\n",
    "            bq, nq = nq, set()\n",
    "            if len(bq) > len(eq):\n",
    "                bq, eq = eq, bq\n",
    "        return 0\n",
    "\n",
    "    def ladderLengthBFS(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        visitor = set()\n",
    "        wordList = set(wordList)\n",
    "        n = len(beginWord)\n",
    "        q = [beginWord]\n",
    "        visitor.add(beginWord)\n",
    "        cnt = 1\n",
    "        while q:\n",
    "            nq = []\n",
    "            for word in q:\n",
    "                for new_word in [word[:i] + c + word[i + 1:] for i in range(n) for c in string.ascii_lowercase]:\n",
    "                    if new_word not in wordList:\n",
    "                        continue\n",
    "                    if new_word == endWord:\n",
    "                        return cnt + 1\n",
    "                    if new_word not in visitor:\n",
    "                        visitor.add(new_word)\n",
    "                        nq.append(new_word)\n",
    "            cnt += 1\n",
    "            q = nq\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        word_num = len(wordList)\n",
    "        word_len = len(beginWord)\n",
    "        flag = [0] * word_num\n",
    "\n",
    "        def cal_dis(word1, word2):\n",
    "            dis = 0\n",
    "            for i in range(word_len):\n",
    "                if word1[i] != word2[i]:\n",
    "                    dis += 1\n",
    "                    if dis > 1:\n",
    "                        break\n",
    "            return dis\n",
    "        \n",
    "        if cal_dis(endWord, beginWord) == 1:\n",
    "            return 2\n",
    "\n",
    "        def get_transfer_word(word1, trans_set):\n",
    "            for j in range(word_num):\n",
    "                if flag[j] != 0:\n",
    "                    continue\n",
    "                dis = cal_dis(word1, wordList[j])\n",
    "                if dis == 1:\n",
    "                    if cal_dis(beginWord, wordList[j]) == 1:\n",
    "                        return None\n",
    "                    trans_set.add(wordList[j])\n",
    "                    flag[j] = 1\n",
    "            return 1\n",
    "        \n",
    "        depth = 3\n",
    "        word_list = set([endWord])\n",
    "        while len(word_list) > 0:\n",
    "            tmp_list = set()\n",
    "            for word in word_list:\n",
    "                result = get_transfer_word(word, tmp_list)\n",
    "                if result is None:\n",
    "                    return depth\n",
    "            depth += 1\n",
    "            word_list = tmp_list\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        word_dict = set(wordList)\n",
    "        if endWord not in word_dict:\n",
    "            return 0\n",
    "        forward = {beginWord}\n",
    "        backward = {endWord}\n",
    "        layer = 2\n",
    "        len_word = len(beginWord)\n",
    "        letters = string.ascii_lowercase\n",
    "        while forward:\n",
    "            word_dict -= forward\n",
    "            temp_forward = set() # 存储转换后在字典中有对应的词的set()\n",
    "\n",
    "            for word in forward:\n",
    "                for i in range(len_word):\n",
    "                    x, y = word[:i], word[i+1:]\n",
    "                    for letter in letters:\n",
    "                        temp_word = x + letter + y\n",
    "                        if temp_word in backward:\n",
    "                            return layer\n",
    "                        if temp_word in word_dict: # 如果转换的词在字典中\n",
    "                            temp_forward.add(temp_word)\n",
    "            layer += 1\n",
    "\n",
    "            if len(temp_forward) < len(backward):\n",
    "                # 如果temp_forward 为 空时\n",
    "                forward = temp_forward\n",
    "            else:\n",
    "                # 不为空时，将backward 作为开始， temp_forward作为结尾\n",
    "                forward, backward = backward, temp_forward\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        st = set(wordList)\n",
    "        if endWord not in st:\n",
    "            return 0\n",
    "        m=len(beginWord)\n",
    "        \n",
    "        lqueue = collections.deque()\n",
    "        rqueue = collections.deque()\n",
    "        step = 0\n",
    "        lqueue.append(beginWord)\n",
    "        rqueue.append(endWord)\n",
    "\n",
    "        lvisited,rvisited = set(),set()\n",
    "        lvisited.add(beginWord)\n",
    "        rvisited.add(endWord)\n",
    "        while lqueue and rqueue:\n",
    "            if len(lqueue)>len(rqueue):\n",
    "                lqueue,rqueue = rqueue,lqueue\n",
    "                lvisited,rvisited = rvisited,lvisited\n",
    "            step+=1\n",
    "            for k in range(len(lqueue)):\n",
    "                cur = lqueue.popleft()\n",
    "                if cur in rvisited:\n",
    "                    return step\n",
    "                for i in range(m):\n",
    "                    for j in range(26):\n",
    "                        tmp = cur[:i]+chr(97+j)+cur[i+1:]\n",
    "                        if tmp in st and tmp not in lvisited:\n",
    "                            lqueue.append(tmp)\n",
    "                            lvisited.add(tmp)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        st=set(wordList)\n",
    "        if endWord not in st:\n",
    "            return 0\n",
    "        m=len(beginWord)        \n",
    "\n",
    "        queue=collections.deque()        \n",
    "        queue.append((beginWord,1))\n",
    "\n",
    "        visited=set()\n",
    "        visited.add(beginWord)\n",
    "\n",
    "        while queue:\n",
    "            cur,step=queue.popleft()\n",
    "            if cur==endWord:\n",
    "                return step\n",
    "            \n",
    "            for i in range(m):                \n",
    "                for j in range(26):\n",
    "                    tmp=cur[:i]+chr(97+j)+cur[i+1:]\n",
    "                    if tmp not in visited and tmp in st:\n",
    "                        queue.append((tmp,step+1))\n",
    "                        visited.add(tmp)\n",
    "\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\r\n",
    "        queue = [beginWord]\r\n",
    "        closeSet = set()\r\n",
    "        path = 1\r\n",
    "        while queue:\r\n",
    "            length = len(queue)\r\n",
    "            path += 1\r\n",
    "            for i in range(length):\r\n",
    "                curWord = queue.pop(0)\r\n",
    "                j = 0\r\n",
    "                while j != len(wordList):\r\n",
    "                    if self.__canTransfer(curWord, wordList[j]):\r\n",
    "                        # print(wordList[j])\r\n",
    "                        if wordList[j] == endWord:\r\n",
    "                            return path\r\n",
    "                        queue.append(wordList.pop(j))\r\n",
    "                    else:\r\n",
    "                        j += 1\r\n",
    "        return 0\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "    def __canTransfer(self, word1, word2):\r\n",
    "        count = 0\r\n",
    "        for i in range(len(word1)):\r\n",
    "            if word1[i] != word2[i]:\r\n",
    "                count += 1\r\n",
    "        return count == 1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        q1, q2 = deque(), deque()\n",
    "        v1, v2 = Counter(), Counter()\n",
    "        q1.append(beginWord)\n",
    "        q2.append(endWord)\n",
    "        v1[beginWord] = 1\n",
    "        v2[endWord] = 1\n",
    "        while q1 and q2:\n",
    "            #print(q1, q2)\n",
    "            if len(q1) <= len(q2):\n",
    "                res = self.bfs(q1, v1, v2, wordList)\n",
    "            else:\n",
    "                res = self.bfs(q2, v2, v1, wordList)\n",
    "            if res > 0:\n",
    "                return res\n",
    "        return 0\n",
    "\n",
    "    def getNext(self, word):\n",
    "        word = list(word)\n",
    "        n = len(word)\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                cur = word[i]\n",
    "                word[i] = chr(ord('a') + j)\n",
    "                yield ''.join(word)\n",
    "                word[i] = cur\n",
    "\n",
    "    def bfs(self, q, cur, other, wordList):\n",
    "        for _ in range(len(q)):\n",
    "            word = q.popleft()\n",
    "            step = cur[word]\n",
    "            for s in self.getNext(word):\n",
    "                if s in wordList and s not in cur:\n",
    "                    #print(word, s, q, cur, other)\n",
    "                    if s in other:\n",
    "                        return step + other[s]\n",
    "                    cur[s] = step + 1\n",
    "                    q.append(s)\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        layer=1\n",
    "        wordset=set(wordList)\n",
    "        wordset.add(beginWord)\n",
    "        tempSet={beginWord}\n",
    "        while tempSet:\n",
    "            for s in tempSet:\n",
    "                wordset.discard(s)\n",
    "            layer+=1\n",
    "            tempSet2=set()\n",
    "            for s in tempSet:\n",
    "                for i in range(len(s)):\n",
    "                    ssplit=list(s)\n",
    "                    for idx in range(97,123):\n",
    "                        ssplit[i]=chr(idx)\n",
    "                        s2=''.join(ssplit)\n",
    "                        if s2 in wordset:\n",
    "                            if s2==endWord:\n",
    "                                return layer\n",
    "                            else:\n",
    "                                tempSet2.add(s2)\n",
    "            tempSet=tempSet2\n",
    "        return 0\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList or beginWord == endWord: return 0\n",
    "        find = set(wordList)\n",
    "        used = {i : False for i in wordList}\n",
    "        res = 1\n",
    "        que = deque()\n",
    "        l = len(beginWord)\n",
    "        que.append(beginWord)\n",
    "        while que:\n",
    "            n = len(que)\n",
    "            for _ in range(n):\n",
    "                tmp = que.popleft()\n",
    "                nextWord = list(tmp)\n",
    "                for i in range(l):\n",
    "                    init = nextWord[i]\n",
    "                    for j in range(26):\n",
    "                        nextWord[i] = chr(ord('a') + j)\n",
    "                        newWord = ''.join(nextWord)\n",
    "                        if newWord == endWord:\n",
    "                            return res + 1\n",
    "                        if newWord in find:\n",
    "                            que.append(newWord)\n",
    "                            find.remove(newWord)\n",
    "                    nextWord[i] = init\n",
    "            res += 1\n",
    "        return 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# from collections import deque\n",
    "# class Solution:\n",
    "#     def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "#         if endWord not in wordList: return 0\n",
    "#         if beginWord == endWord: return 0\n",
    "#         def changable(src: str, tgt: str) -> bool:\n",
    "#             num = 0\n",
    "#             if len(src) != len(tgt): return False\n",
    "#             for i in range(len(src)):\n",
    "#                 if src[i] != tgt[i]:\n",
    "#                     num += 1\n",
    "#             return True if num == 1 else False\n",
    "#         change = {}\n",
    "#         used = {}\n",
    "#         change[beginWord] = set()\n",
    "#         for item in wordList:\n",
    "#             if changable(beginWord, item):\n",
    "#                 change[beginWord].add(item)\n",
    "#         if not change[beginWord]:\n",
    "#             return 0\n",
    "#         for i in range(len(wordList)):\n",
    "#             used[wordList[i]] = 0\n",
    "#             change[wordList[i]] = set()\n",
    "#             for j in range(len(wordList)):\n",
    "#                 if j == i: continue\n",
    "#                 if changable(wordList[i], wordList[j]):\n",
    "#                     change[wordList[i]].add(wordList[j])\n",
    "#         res = 1\n",
    "#         que = deque()\n",
    "#         que.append(beginWord)\n",
    "#         while que:\n",
    "#             n = len(que)\n",
    "#             for i in range(n):\n",
    "#                 tmp = que.popleft()\n",
    "#                 for item in change[tmp]:\n",
    "#                     if item == endWord: return res + 1\n",
    "#                     if not used[item]:\n",
    "#                         que.append(item)\n",
    "#                         used[item] = 1\n",
    "#             res += 1\n",
    "#         return 0\n",
    "\n",
    "# class Solution:\n",
    "#     def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "#         def addWord(word: str):\n",
    "#             if word not in wordId:\n",
    "#                 nonlocal nodeNum\n",
    "#                 wordId[word] = nodeNum\n",
    "#                 nodeNum += 1\n",
    "        \n",
    "#         def addEdge(word: str):\n",
    "#             addWord(word)\n",
    "#             id1 = wordId[word]\n",
    "#             chars = list(word)\n",
    "#             for i in range(len(chars)):\n",
    "#                 tmp = chars[i]\n",
    "#                 chars[i] = \"*\"\n",
    "#                 newWord = \"\".join(chars)\n",
    "#                 addWord(newWord)\n",
    "#                 id2 = wordId[newWord]\n",
    "#                 edge[id1].append(id2)\n",
    "#                 edge[id2].append(id1)\n",
    "#                 chars[i] = tmp\n",
    "#             #print(wordId, edge)\n",
    "\n",
    "#         wordId = dict()\n",
    "#         edge = collections.defaultdict(list)\n",
    "#         nodeNum = 0\n",
    "\n",
    "#         for word in wordList:\n",
    "#             addEdge(word)\n",
    "        \n",
    "#         addEdge(beginWord)\n",
    "#         if endWord not in wordId:\n",
    "#             return 0\n",
    "        \n",
    "#         dis = [float(\"inf\")] * nodeNum\n",
    "#         beginId, endId = wordId[beginWord], wordId[endWord]\n",
    "#         dis[beginId] = 0\n",
    "\n",
    "#         que = collections.deque([beginId])\n",
    "#         while que:\n",
    "#             x = que.popleft()\n",
    "#             if x == endId:\n",
    "#                 return dis[endId] // 2 + 1\n",
    "#             for it in edge[x]:\n",
    "#                 if dis[it] == float(\"inf\"):\n",
    "#                     dis[it] = dis[x] + 1\n",
    "#                     que.append(it)\n",
    "        \n",
    "#         return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def update(d,cur,other):\n",
    "            m = len(d)\n",
    "            while m > 0:\n",
    "                poll = d.pop()\n",
    "                n = len(poll)\n",
    "                for i in range(n):\n",
    "                    for j in range(26):\n",
    "                        sub = poll[:i] + chr(ord('a') + j) + poll[i + 1:]\n",
    "                        if sub in wordList:\n",
    "                            #如果在当前方向出现过，跳过\n",
    "                            if sub in cur and cur[sub] <= cur[poll] + 1:\n",
    "                                continue\n",
    "                            if sub in other:\n",
    "                                return cur[poll] + other[sub] + 1\n",
    "                            else:\n",
    "                                d.appendleft(sub)\n",
    "                                cur[sub] = cur[poll] + 1\n",
    "                m -= 1\n",
    "            return -1\n",
    "        def bfs():\n",
    "            #d1表示从beginword开始搜索\n",
    "            #d2表示从endword开始搜索\n",
    "            d1 = deque()\n",
    "            d2 = deque()\n",
    "            #m1和m2分别记录两个方向出现的单词经过多少次转换得到\n",
    "            m1 = defaultdict(int)\n",
    "            m2 = defaultdict(int)\n",
    "            d1.appendleft(beginWord)\n",
    "            m1[beginWord] = 0\n",
    "            d2.appendleft(endWord)\n",
    "            m2[endWord] = 0\n",
    "            #只有都不为空才搜索，一个为空说明一边搜到底都不到endword\n",
    "            while d1 and d2:\n",
    "                t = -1\n",
    "                #为了使两边搜索平均，优先拓展队列内元素少的方向\n",
    "                if len(d1) <= len(d2):\n",
    "                    t = update(d1,m1,m2)\n",
    "                else:\n",
    "                    t = update(d2,m2,m1)\n",
    "                if t != -1:\n",
    "                    return t\n",
    "            return -1\n",
    "            \n",
    "\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        ans = bfs()\n",
    "        return 0 if ans == -1 else ans + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList: \n",
    "            return 0\n",
    "        deque = collections.deque([beginWord])\n",
    "        vis = set([beginWord])\n",
    "        distance = 0\n",
    "    \n",
    "        while deque:\n",
    "            distance += 1\n",
    "            size = len(deque)\n",
    "            for _ in range(size):\n",
    "                word = deque.popleft()\n",
    "                if word == endWord:\n",
    "                    return distance\n",
    "                for next_word in self.get_next_word_list(word, wordList):\n",
    "                    if next_word in vis:\n",
    "                        continue\n",
    "                    deque.append(next_word)\n",
    "                    vis.add(next_word)\n",
    "        return 0\n",
    "\n",
    "    def get_next_word_list(self, word: str, wordList: List[str]):\n",
    "        next_word_list = []\n",
    "        \n",
    "        for next_word in wordList:\n",
    "            one_different = False\n",
    "            for x in range(len(word)):\n",
    "                if word[x] != next_word[x]:\n",
    "                    if one_different:\n",
    "                        one_different = False\n",
    "                        break\n",
    "                    one_different = True\n",
    "            if one_different:\n",
    "                next_word_list.append(next_word)\n",
    "        return next_word_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if beginWord == endWord:\n",
    "            return 1\n",
    "\n",
    "        wordList = set(wordList)\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        q = deque([(beginWord, 1)])\n",
    "\n",
    "        while q:\n",
    "            cur, step = q.popleft()\n",
    "            for i, x in enumerate(cur):\n",
    "                for y in range(97, 123):\n",
    "                    y = chr(y)\n",
    "                    if x != y:\n",
    "                        nxt = cur[:i] + y + cur[i+1:]\n",
    "                        if nxt == endWord:\n",
    "                            return step + 1\n",
    "                        if nxt in wordList:\n",
    "                            q.append((nxt, step+1))\n",
    "                            wordList.remove(nxt)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        wordSet = set(wordList)\n",
    "        if endWord not in wordSet: return 0\n",
    "        n = len(beginWord)\n",
    "        step = 1\n",
    "        frontier = [beginWord]\n",
    "        used = {beginWord}\n",
    "        while frontier:\n",
    "            next = []\n",
    "            for f in frontier:\n",
    "                for word in wordList:\n",
    "                    if word == endWord and self.dist(word, f) == 1:\n",
    "                        print (word, frontier, step)\n",
    "                        return step+1\n",
    "                    if word not in used and self.dist(word, f) == 1:\n",
    "                        used.add(word)\n",
    "                        next.append(word)\n",
    "            step += 1\n",
    "            frontier = next\n",
    "            print(frontier, step)\n",
    "        return 0\n",
    "\n",
    "    def dist(self, w1, w2):\n",
    "        l1 = len(w1)\n",
    "        c = 0\n",
    "        for i in range(l1):\n",
    "            if w1[i] != w2[i]:\n",
    "                c += 1\n",
    "        return c == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        wordList=set(wordList)\n",
    "        if endWord not in wordList:return 0\n",
    "        q, visited = [(beginWord, 1)], set()\n",
    "        while q:\n",
    "            word, step = q.pop(0)\n",
    "            if word not in visited:\n",
    "                visited.add(word)\n",
    "                if word == endWord:\n",
    "                    return step\n",
    "                for i in range(len(word)):\n",
    "                    for j in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                        tmp = word[:i] + j + word[i+1:]\n",
    "                        if tmp in wordList and tmp not in visited: # difference\n",
    "                            q.append((tmp, step + 1))\n",
    "\n",
    "        return 0 \n",
    "\n",
    "\n",
    "        # step=0\n",
    "        # length=len(beginWord)\n",
    "        # cur_words=[beginWord]\n",
    "        # visited=[]\n",
    "\n",
    "        # while cur_words:\n",
    "        #     try_words=[]\n",
    "        #     visited.extend(cur_words)\n",
    "        #     for word in cur_words:\n",
    "        #         # 找word一步可达的词\n",
    "        #         for i in range(length):\n",
    "        #             for j in 'abcdefghijklmnopqrstuvwxyz':\n",
    "        #                 tmp = word[:i] + j + word[i+1:]\n",
    "        #                 if tmp not in visited and tmp in wordList:\n",
    "        #                     try_words.append(tmp)\n",
    "        #     cur_words=try_words\n",
    "        #     step+=1\n",
    "        #     if endWord in cur_words:return step+1\n",
    "        #     if len(cur_words)==0:return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        N = len(wordList)\n",
    "        w2i = dict([(wordList[i],i) for i in range(N)])\n",
    "        if endWord not in w2i:\n",
    "            return 0 \n",
    "        if beginWord not in w2i:\n",
    "            wordList.append(beginWord)\n",
    "            s = N \n",
    "        else:\n",
    "            s = w2i[beginWord]\n",
    "        e = w2i[endWord]\n",
    "        graph = defaultdict(list)\n",
    "        for i in range(len(wordList)):\n",
    "            w1 = wordList[i]\n",
    "            for j in range(i+1,len(wordList)):\n",
    "                w2 = wordList[j]\n",
    "                cnt = 0\n",
    "                for k in range(len(w1)):\n",
    "                    if w1[k]!=w2[k]:\n",
    "                        cnt+=1 \n",
    "                    if cnt>=2:\n",
    "                        break \n",
    "                if cnt==1:\n",
    "                    graph[i].append(j)\n",
    "                    graph[j].append(i)\n",
    "        if e not in graph:\n",
    "            return 0\n",
    "        heap = deque()\n",
    "        heap.append([0,s])\n",
    "        check = set([s])\n",
    "        # print(heap,s)\n",
    "        while len(heap)>0:\n",
    "            # print(heap,s,e)\n",
    "            l,f = heap.popleft()\n",
    "            if f==e:\n",
    "                return l+1\n",
    "            for t in graph[f]:\n",
    "                # print(t,check)\n",
    "                if t not in check:\n",
    "                    heap.append([l+1,t])\n",
    "                    check.add(t)\n",
    "\n",
    "        \n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        from collections import deque\n",
    "        word_set = set(wordList)\n",
    "        if endWord not in word_set:\n",
    "            return 0\n",
    "        letters = [chr(ord('a') + i) for i in range(26)]\n",
    "        q = deque([(beginWord, 1)])\n",
    "        visited = set()\n",
    "        while len(q) > 0:\n",
    "            top, dis = q.popleft()\n",
    "            if top == endWord:\n",
    "                return dis\n",
    "            if top in visited:\n",
    "                continue\n",
    "            visited.add(top)\n",
    "            ch_list = list(top)\n",
    "            for i, ch in enumerate(ch_list):\n",
    "                for letter in letters:\n",
    "                    if letter == ch:\n",
    "                        continue\n",
    "                    ch_list[i] = letter\n",
    "                    new_str = ''.join(ch_list)\n",
    "                    ch_list[i] = ch\n",
    "                    if new_str not in word_set:\n",
    "                        continue\n",
    "                    q.append((new_str, dis + 1))\n",
    "        return 0\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dis1(a,b):\n",
    "    n=0\n",
    "    for i in range(len(a)):\n",
    "        if a[i]!=b[i]:\n",
    "            n+=1\n",
    "            if n>1:\n",
    "                return False\n",
    "    if n==1:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def words(bw,ew,wl):\n",
    "    if ew not in wl:\n",
    "        return 0\n",
    "    wl=[bw,*wl]\n",
    "    dis1dic={}\n",
    "    sz=len(wl)\n",
    "    for i in range(sz):\n",
    "        for j in range(i+1,sz):\n",
    "            if dis1(wl[i],wl[j]):\n",
    "                if wl[i] not in dis1dic:\n",
    "                    dis1dic[wl[i] ]=[wl[j]]\n",
    "                else:\n",
    "                    dis1dic[wl[i]].append(wl[j])\n",
    "                if wl[j] not in dis1dic:\n",
    "                    dis1dic[wl[j] ]=[wl[i]]\n",
    "                else:\n",
    "                    dis1dic[wl[j]].append(wl[i]) \n",
    "    if bw not in dis1dic:\n",
    "        return 0\n",
    "    \n",
    "    beginSearch=[bw]\n",
    "    \n",
    "    def search(beginSearch):\n",
    "        disF={}\n",
    "        sn=1\n",
    "        find=False\n",
    "        searched=set([beginSearch[0]])\n",
    "        returnDic={}\n",
    "        while not find and sn<sz+1:\n",
    "           \n",
    "            tempsearch=set()\n",
    "            for ser in beginSearch:\n",
    "                s=ser\n",
    "                for k in dis1dic[s]:\n",
    "                    if k not in searched:\n",
    "                        if k not in returnDic:  \n",
    "                            returnDic[k]=set([s])\n",
    "                        else:\n",
    "                            returnDic[k].add(s)\n",
    "                        vv=k\n",
    "                        if sn not in disF:\n",
    "                            disF[sn]=set([vv])\n",
    "                        else:\n",
    "                            disF[sn].add(vv)\n",
    "                        if k==ew:\n",
    "                            find=True\n",
    "                        tempsearch.add(k)\n",
    "            #print(disF[sn])\n",
    "            searched=searched|tempsearch\n",
    "            if find:\n",
    "                break\n",
    "            else:\n",
    "                if not sn in disF:\n",
    "                    return 0\n",
    "                beginSearch=disF[sn]\n",
    "                sn+=1\n",
    "     \n",
    "        if not find:\n",
    "            return 0\n",
    "        #print(disF[sn])\n",
    "        \n",
    "        return sn+1\n",
    "        \n",
    "    return search(beginSearch)\n",
    "    \n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        return words( beginWord,endWord,wordList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        \n",
    "        all_combo_dict = defaultdict(list)\n",
    "        for word in wordList:\n",
    "            for i in range(len(beginWord)):\n",
    "                all_combo_dict[word[:i]+'*'+word[i+1:]].append(word)\n",
    "\n",
    "        visited = set([beginWord])\n",
    "        queue = [beginWord]\n",
    "        length = 0\n",
    "        while queue:\n",
    "            length += 1\n",
    "            size = len(queue)\n",
    "            while size:\n",
    "                cur = queue.pop(0)\n",
    "                size -= 1\n",
    "                for i in range(len(cur)):\n",
    "                    intermediate_word = cur[:i]+'*'+cur[i+1:]\n",
    "                    for nex in all_combo_dict[intermediate_word]:\n",
    "                        if nex == endWord:\n",
    "                            return length + 1\n",
    "                        if nex not in visited:\n",
    "                            visited.add(nex)\n",
    "                            queue.append(nex)\n",
    "                    all_combo_dict[intermediate_word] = []\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "from typing import Tuple, List\n",
    "class Queue:\n",
    "    \"\"\"记忆化BFS队列\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        self.queue = deque()\n",
    "        self.vis = {}\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self.queue)\n",
    "    \n",
    "    def __contains__(self, x: str) -> bool:\n",
    "        \"\"\"判断某个状态是否已经遍历过\n",
    "\n",
    "        Args:\n",
    "            x (str): 状态\n",
    "\n",
    "        Returns:\n",
    "            bool: 是否遍历\n",
    "        \"\"\"\n",
    "        return x in self.vis\n",
    "    \n",
    "    def add(self, x: Tuple[str, int]) -> None:\n",
    "        \"\"\"添加状态和对应步长\n",
    "\n",
    "        Args:\n",
    "            x (Tuple[str, int]): 状态+步长\n",
    "        \"\"\"\n",
    "        self.queue.append(x[0])\n",
    "        self.vis[x[0]] = x[1]\n",
    "    \n",
    "    def pop(self) -> Tuple[str, int]:\n",
    "        \"\"\"弹出状态和步长\n",
    "\n",
    "        Returns:\n",
    "            Tuple[str, int]: 状态和步长\n",
    "        \"\"\"\n",
    "        return self.queue.popleft()\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        wordList = set(wordList)\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        for word in wordList:\n",
    "            for i in range(len(word)):\n",
    "                d[word[:i] + '*' + word[i + 1:]].append(word)\n",
    "\n",
    "        begin = Queue()\n",
    "        end = Queue()\n",
    "        begin.add((beginWord, 1))\n",
    "        end.add((endWord, 1))\n",
    "\n",
    "        def get_next(word):\n",
    "            nxt = []\n",
    "            for i in range(len(word)):\n",
    "                tmp = word[:i] + '*' + word[i + 1:]\n",
    "                if tmp in d:\n",
    "                    for w in d[tmp]:\n",
    "                        nxt.append(w)\n",
    "            return nxt\n",
    "\n",
    "        while begin and end:\n",
    "            if len(begin) > len(end):\n",
    "                ts, te = end, begin\n",
    "            else:\n",
    "                ts, te = begin, end\n",
    "            word = ts.pop()\n",
    "            for nxt in get_next(word):\n",
    "                if nxt in ts:\n",
    "                    continue\n",
    "                if nxt in te.vis:\n",
    "                    return ts.vis[word] + te.vis[nxt]\n",
    "                ts.add((nxt, ts.vis[word] + 1))\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "from typing import Tuple, List\n",
    "class Queue:\n",
    "    \"\"\"记忆化BFS队列\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        self.queue = deque()\n",
    "        self.vis = {}\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self.queue)\n",
    "    \n",
    "    def __contains__(self, x: str) -> bool:\n",
    "        \"\"\"判断某个状态是否已经遍历过\n",
    "\n",
    "        Args:\n",
    "            x (str): 状态\n",
    "\n",
    "        Returns:\n",
    "            bool: 是否遍历\n",
    "        \"\"\"\n",
    "        return x in self.vis\n",
    "    \n",
    "    def add(self, x: Tuple[str, int]) -> None:\n",
    "        \"\"\"添加状态和对应步长\n",
    "\n",
    "        Args:\n",
    "            x (Tuple[str, int]): 状态+步长\n",
    "        \"\"\"\n",
    "        self.queue.append(x[0])\n",
    "        self.vis[x[0]] = x[1]\n",
    "    \n",
    "    def pop(self) -> Tuple[str, int]:\n",
    "        \"\"\"弹出状态和步长\n",
    "\n",
    "        Returns:\n",
    "            Tuple[str, int]: 状态和步长\n",
    "        \"\"\"\n",
    "        return self.queue.popleft()\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        wordList = set(wordList)\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        for word in wordList:\n",
    "            for i in range(len(word)):\n",
    "                d[word[:i] + '*' + word[i + 1:]].append(word)\n",
    "\n",
    "        begin = Queue()\n",
    "        end = Queue()\n",
    "        begin.add((beginWord, 1))\n",
    "        end.add((endWord, 1))\n",
    "\n",
    "        def get_next(word):\n",
    "            nxt = []\n",
    "            for i in range(len(word)):\n",
    "                tmp = word[:i] + '*' + word[i + 1:]\n",
    "                if tmp in d:\n",
    "                    for w in d[tmp]:\n",
    "                        nxt.append(w)\n",
    "            return nxt\n",
    "\n",
    "        while begin and end:\n",
    "            if len(begin) > len(end):\n",
    "                ts, te = end, begin\n",
    "            else:\n",
    "                ts, te = begin, end\n",
    "            word = ts.pop()\n",
    "            for nxt in get_next(word):\n",
    "                if nxt in ts:\n",
    "                    continue\n",
    "                if nxt in te.vis:\n",
    "                    return ts.vis[word] + te.vis[nxt]\n",
    "                ts.add((nxt, ts.vis[word] + 1))\n",
    "        return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        import collections\n",
    "        n=len(beginWord)\n",
    "        gragh=collections.defaultdict(list)\n",
    "        for word in wordList:\n",
    "            for i in range(n):\n",
    "                gragh[word[:i] + '*' + word[i+1:]].append(word)\n",
    "        print(gragh)\n",
    "        queue = [(beginWord,1)]\n",
    "        visited = {beginWord:True}\n",
    "        #print(queue)\n",
    "        while queue:\n",
    "            current_word,level = queue.pop(0)\n",
    "            print(current_word,level)\n",
    "            for i in range(n):\n",
    "                intermediate_word = current_word[:i] + '*' + current_word[i+1:]\n",
    "                for word in gragh[intermediate_word]:\n",
    "                    if word == endWord:\n",
    "                        return level + 1\n",
    "                    if word not in visited:\n",
    "                        visited[word] = True\n",
    "                        queue.append((word,level+1))\n",
    "                gragh[intermediate_word] = []\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        L = len(beginWord)\n",
    "        nodes = defaultdict(list)\n",
    "        for i, word in enumerate(wordList):\n",
    "            for j in range(L):\n",
    "                tag = (word[:j] + word[j + 1:], j)\n",
    "                nodes[tag].append(i)\n",
    "        queue = [-1]\n",
    "        new_queue = []\n",
    "        distance = 1\n",
    "        vis = [False] * len(wordList)\n",
    "        while len(queue) > 0:\n",
    "            distance += 1\n",
    "            for idx in queue:\n",
    "                word = wordList[idx] if idx >= 0 else beginWord\n",
    "                for j in range(L):\n",
    "                    tag = (word[:j] + word[j + 1:], j)\n",
    "                    if tag in nodes:\n",
    "                        for jdx in nodes[tag]:\n",
    "                            if not vis[jdx]:\n",
    "                                if wordList[jdx] == endWord:\n",
    "                                    return distance\n",
    "                                new_queue.append(jdx)\n",
    "                                vis[jdx] = True\n",
    "                        del nodes[tag]\n",
    "            queue = new_queue\n",
    "            new_queue = []\n",
    "        return 0                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # endword不一定在wordlist中\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        n = 0\n",
    "        word2num = dict()\n",
    "        def addWord(w):\n",
    "            if w not in word2num:\n",
    "                nonlocal n\n",
    "                word2num[w] = n\n",
    "                n += 1\n",
    "\n",
    "        edge = collections.defaultdict(list)\n",
    "        def addEdge(w):\n",
    "            addWord(w)\n",
    "            id1 = word2num[w]\n",
    "            chars = list(w)\n",
    "            # 将w中的一个字符替换为*，构造虚拟结点\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = \"*\"\n",
    "                newWord = \"\".join(chars)\n",
    "                addWord(newWord)\n",
    "                id2 = word2num[newWord]\n",
    "                edge[id1].append(id2) # 只需要构建与虚拟结点之间的边即可\n",
    "                edge[id2].append(id1)\n",
    "                chars[i] = tmp\n",
    "\n",
    "        # 建图\n",
    "        for w in wordList:\n",
    "            addEdge(w)\n",
    "        # beginword不一定在wordlist中，需要单独建边\n",
    "        addEdge(beginWord)\n",
    " \n",
    "        \n",
    "        dis = [float(\"inf\")] * n\n",
    "        beginId, endId = word2num[beginWord], word2num[endWord]\n",
    "        dis[beginId] = 0  # dis[id]表示从begin出发到id的距离\n",
    "\n",
    "        que = deque([beginId])\n",
    "        while que:\n",
    "            x = que.popleft()  # 取出队首元素\n",
    "            if x == endId:  # 找到目标单词\n",
    "                return dis[endId] // 2 + 1\n",
    "            # 如果邻接结点还未访问，则访问\n",
    "            # 否则不访问(先前已经访问过更短路了)\n",
    "            for it in edge[x]:\n",
    "                if dis[it] == float(\"inf\"):\n",
    "                    dis[it] = dis[x] + 1\n",
    "                    que.append(it)\n",
    "        \n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        n = 0\n",
    "        wn = dict()\n",
    "        def wtn(w):\n",
    "            if w not in wn:\n",
    "                nonlocal n\n",
    "                wn[w] = n\n",
    "                n += 1\n",
    "        \n",
    "        edge = defaultdict(list)\n",
    "        def wtc(w):\n",
    "            wl = list(w)\n",
    "            wtn(w)\n",
    "            id1 = wn[w]\n",
    "            for i in range(len(wl)):\n",
    "                tmp = wl[i]\n",
    "                wl[i] = \"*\"\n",
    "                nw = \"\".join(wl)\n",
    "                wtn(nw)\n",
    "                id2 = wn[nw]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1)\n",
    "                wl[i] = tmp\n",
    "        \n",
    "\n",
    "        for w in wordList:\n",
    "            wtc(w)\n",
    "        wtc(beginWord)\n",
    "\n",
    "        dis = [inf] * len(wn)\n",
    "        bid, eid = wn[beginWord], wn[endWord]\n",
    "        dis[bid] = 0\n",
    "        q = deque([bid])\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            if x == eid:\n",
    "                return (dis[x] // 2) + 1\n",
    "            for nx in edge[x]:\n",
    "                if dis[nx] == inf:\n",
    "                    dis[nx] = dis[x] + 1\n",
    "                    q.append(nx)\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        if beginWord not in wordList:\n",
    "            wordList.append(beginWord)\n",
    "        n = len(beginWord)\n",
    "        hashAll = {}\n",
    "        hashNext = {}\n",
    "        hashVisited = {}\n",
    "        dp = {}\n",
    "        for i in range(n):\n",
    "            hashAll[i] = {}\n",
    "        for word in wordList:\n",
    "            for i in range(n):\n",
    "                s = word[:i] + word[i+1:]\n",
    "                if s not in hashAll[i].keys():\n",
    "                    hashAll[i][s] = []\n",
    "                hashAll[i][s].append(word)\n",
    "            hashNext[word] = set()\n",
    "            hashVisited[word] = 0\n",
    "            dp[word] = 5002\n",
    "        for word in wordList:\n",
    "            for i in range(n):\n",
    "                s = word[:i] + word[i+1:]\n",
    "                adjacentWords = hashAll[i][s]\n",
    "                for item in adjacentWords:\n",
    "                    if item != word:\n",
    "                        hashNext[word].add(item)\n",
    "        # hashNext[beginWord] = set()\n",
    "        # for i in range(n):\n",
    "        #     s = beginWord[:i] + beginWord[i+1:]\n",
    "        #     if s not in hashAll[i].keys():\n",
    "        #         continue\n",
    "        #     adjacentWords = hashAll[i][s]\n",
    "        #     for item in adjacentWords:\n",
    "        #         if item != beginWord:\n",
    "        #             hashNext[beginWord].add(item)\n",
    "        \n",
    "        adjacentWords = hashNext[endWord]\n",
    "        level = 2\n",
    "        hashVisited[endWord] = 1\n",
    "        while True:\n",
    "            expand_word = []\n",
    "            updateFlag = False\n",
    "            for word in adjacentWords:\n",
    "                if hashVisited[word] == 0:\n",
    "                    dp[word] = level\n",
    "                    updateFlag = True\n",
    "                    expand_word.append(word)\n",
    "            if updateFlag == False:\n",
    "                return 0\n",
    "            if dp[beginWord] < 5002:\n",
    "                return dp[beginWord]\n",
    "            level += 1\n",
    "            adjacentWords = set()\n",
    "            for word in expand_word:\n",
    "                tmpList = hashNext[word]\n",
    "                for item in tmpList:\n",
    "                    adjacentWords.add(item)\n",
    "            adjacentWords = list(adjacentWords)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def dfs(beginWord,endWord):\n",
    "        #     res = 5002\n",
    "        #     adjacentWords = hashNext[beginWord]\n",
    "        #     if endWord in adjacentWords:\n",
    "        #         return 2\n",
    "        #     for word in adjacentWords:\n",
    "        #         if hashVisited[word] == 1:\n",
    "        #             continue\n",
    "        #         else:\n",
    "        #             hashVisited[word] = 1\n",
    "        #             localRes = dfs(word,endWord)\n",
    "        #             hashVisited[word] = 0\n",
    "        #             if localRes != 0:\n",
    "        #                 if localRes + 1 < res:\n",
    "        #                     res = localRes + 1\n",
    "        #     if res == 0 or res == 5002:\n",
    "        #         return 0\n",
    "        #     else:\n",
    "        #         return res\n",
    "        # if beginWord in wordList:\n",
    "        #     hashVisited[beginWord] = 1\n",
    "        # return dfs(beginWord,endWord)\n",
    "                    \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # 如果endWord不在wordList里则返回0\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        n = 0\n",
    "        word_dict = {}\n",
    "\n",
    "        def add_word(w):\n",
    "            nonlocal n\n",
    "            if w not in word_dict:\n",
    "                word_dict[w] = n\n",
    "                n += 1\n",
    "\n",
    "        edge_dict = collections.defaultdict(list)\n",
    "        def add_edge(w):\n",
    "            add_word(w)\n",
    "\n",
    "            w_idx = word_dict.get(w)\n",
    "            \n",
    "            char_list = list(w)\n",
    "            rpl_char_list = copy.deepcopy(char_list)\n",
    "            tmp_l = len(char_list)\n",
    "\n",
    "            for i in range(len(char_list)):\n",
    "                rpl_char_list[i] = '*'\n",
    "                tmp_w = ''.join(rpl_char_list)\n",
    "\n",
    "                add_word(tmp_w)\n",
    "                tmp_idx = word_dict.get(tmp_w)\n",
    "\n",
    "                edge_dict[tmp_idx].append(w_idx)\n",
    "                edge_dict[w_idx].append(tmp_idx)\n",
    "\n",
    "                # rpl_char_list = copy.deepcopy(char_list)\n",
    "                rpl_char_list[i] = char_list[i]\n",
    "\n",
    "        add_edge(beginWord)\n",
    "        for w in wordList:\n",
    "            add_edge(w)\n",
    "\n",
    "        need_step_list = [float('inf') for _ in range(n)]  # 从begin单词到编号n的单词的转换次数\n",
    "\n",
    "        begin_idx = word_dict.get(beginWord)\n",
    "        travel_queue = deque([begin_idx])\n",
    "        need_step_list[begin_idx] = 0  # 初始化\n",
    "\n",
    "        while travel_queue:\n",
    "            travel_idx = travel_queue.popleft()\n",
    "\n",
    "            # if travel_idx == word_dict.get(endWord):  # 说明已经找到endWord节点了\n",
    "            #     return need_step_list[travel_idx] // 2 + 1  # 因为要输出的是层数？\n",
    "\n",
    "            neighbor_list = edge_dict.get(travel_idx)\n",
    "\n",
    "            for n in neighbor_list:\n",
    "                if need_step_list[n] > need_step_list[travel_idx] + 1:  # 当前的次数就是need_step_list[travel_idx] + 1，如果之前的次数比当前小，那就保留，如果大，那就用当前的次数覆盖\n",
    "                    need_step_list[n] = need_step_list[travel_idx] + 1\n",
    "                    if n == word_dict.get(endWord):\n",
    "                        return need_step_list[n] // 2 + 1\n",
    "                    travel_queue.append(n)\n",
    "\n",
    "        return 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # 如果endWord不在wordList里则返回0\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        n = 0\n",
    "        word_dict = {}\n",
    "\n",
    "        def add_word(w):\n",
    "            nonlocal n\n",
    "            if w not in word_dict:\n",
    "                word_dict[w] = n\n",
    "                n += 1\n",
    "\n",
    "        edge_dict = collections.defaultdict(list)\n",
    "        def add_edge(w):\n",
    "            add_word(w)\n",
    "\n",
    "            w_idx = word_dict.get(w)\n",
    "            \n",
    "            char_list = list(w)\n",
    "            rpl_char_list = copy.deepcopy(char_list)\n",
    "            tmp_l = len(char_list)\n",
    "\n",
    "            for i in range(len(char_list)):\n",
    "                rpl_char_list[i] = '*'\n",
    "                tmp_w = ''.join(rpl_char_list)\n",
    "\n",
    "                add_word(tmp_w)\n",
    "                tmp_idx = word_dict.get(tmp_w)\n",
    "\n",
    "                edge_dict[tmp_idx].append(w_idx)\n",
    "                edge_dict[w_idx].append(tmp_idx)\n",
    "\n",
    "                rpl_char_list = copy.deepcopy(char_list)\n",
    "\n",
    "        add_edge(beginWord)\n",
    "        for w in wordList:\n",
    "            add_edge(w)\n",
    "\n",
    "        need_step_list = [float('inf') for _ in range(n)]  # 从begin单词到编号n的单词的转换次数\n",
    "\n",
    "        begin_idx = word_dict.get(beginWord)\n",
    "        travel_queue = deque([begin_idx])\n",
    "        need_step_list[begin_idx] = 0  # 初始化\n",
    "\n",
    "        while travel_queue:\n",
    "            travel_idx = travel_queue.popleft()\n",
    "\n",
    "            # if travel_idx == word_dict.get(endWord):  # 说明已经找到endWord节点了\n",
    "            #     return need_step_list[travel_idx] // 2 + 1  # 因为要输出的是层数？\n",
    "\n",
    "            neighbor_list = edge_dict.get(travel_idx)\n",
    "\n",
    "            for n in neighbor_list:\n",
    "                if need_step_list[n] > need_step_list[travel_idx] + 1:  # 当前的次数就是need_step_list[travel_idx] + 1，如果之前的次数比当前小，那就保留，如果大，那就用当前的次数覆盖\n",
    "                    need_step_list[n] = need_step_list[travel_idx] + 1\n",
    "                    if n == word_dict.get(endWord):\n",
    "                        return need_step_list[n] // 2 + 1\n",
    "                    travel_queue.append(n)\n",
    "\n",
    "        return 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList) -> int:\n",
    "\n",
    "        if endWord not in wordList: return 0\n",
    "\n",
    "        end_id = wordList.index(endWord)+1\n",
    "        ALL = [beginWord] + wordList\n",
    "\n",
    "        # 创建虚拟结点，并在这个过程中创建邻接表\n",
    "        vs = []\n",
    "        adj = defaultdict(lambda :[])\n",
    "        N = len(ALL)  # 虚拟结点的下标从N开始\n",
    "        L = len(beginWord)\n",
    "        for id, word in enumerate(ALL):\n",
    "            for i in range(L):\n",
    "                v = word[:i] + '*' + word[i+1:]\n",
    "                if v not in vs:\n",
    "                    vs.append(v)\n",
    "                    v_id = len(vs)-1 + N\n",
    "                else:\n",
    "                    v_id = vs.index(v) + N\n",
    "                adj[id].append(v_id)\n",
    "                adj[v_id].append(id)\n",
    "\n",
    "        # BFS\n",
    "        q = queue.Queue()\n",
    "        q.put(0)\n",
    "        step = 1\n",
    "        visited = set([0])\n",
    "        while not q.empty():  # 一个非常标准的输出step数的bfs\n",
    "            for _ in range(q.qsize()):\n",
    "                h = q.get()\n",
    "                for d in adj[h]:\n",
    "                    if d == end_id:\n",
    "                        return int(step/2)+1  # 运行到这里时step一定是偶数，所以没影响\n",
    "                    elif d not in visited:\n",
    "                        q.put(d)\n",
    "                        visited.add(d)\n",
    "            step += 1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # https://leetcode.cn/problems/word-ladder/solutions/110710/python-shen-du-jiang-jie-bfsde-jie-gou-by-allen-23/\n",
    "\n",
    "        n = len(beginWord)\n",
    "\n",
    "        # 提前构造查询字段，避免比较两个单词是否相邻（会超时）\n",
    "        mp = defaultdict(list)\n",
    "        for word in wordList:\n",
    "            for i in range(n):\n",
    "                key = word[:i] + '_' + word[i+1:] # 第i位用下划线替换，同一个key的，属于相邻\n",
    "                mp[key].append(word)\n",
    "        \n",
    "        queue = [(beginWord, 1)]\n",
    "        visited = defaultdict(bool)\n",
    "        visited[beginWord] = True\n",
    "\n",
    "        while queue:\n",
    "            curr, level = queue.pop(0)\n",
    "            for i in range(n):\n",
    "                key = curr[:i] + '_' + curr[i+1:]\n",
    "                new_level = level + 1\n",
    "                for neighbour in mp[key]:\n",
    "                    if neighbour == endWord:\n",
    "                        return new_level\n",
    "                    if not visited[neighbour]:\n",
    "                        visited[neighbour] = True\n",
    "                        queue.append((neighbour, new_level))\n",
    "        return 0\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "class Solution(object):\n",
    "    def ladderLength(self, beginWord, endWord, wordList):\n",
    "        size, general_dic = len(beginWord), defaultdict(list)\n",
    "        for w in wordList:\n",
    "            for _ in range(size):\n",
    "                general_dic[w[:_]+\"*\"+w[_+1:]].append(w)\n",
    "        queue = deque()\n",
    "        queue.append((beginWord, 1))  \n",
    "        mark_dic = defaultdict(bool)  \n",
    "        mark_dic[beginWord] = True\n",
    "        while queue:\n",
    "            cur_word, level = queue.popleft()  \n",
    "            for i in range(size):              \n",
    "                for neighbour in general_dic[cur_word[:i]+\"*\"+cur_word[i+1:]]:\n",
    "                    if neighbour == endWord: return level + 1\n",
    "                    if not mark_dic[neighbour]:\n",
    "                        mark_dic[neighbour] = True\n",
    "                        queue.append((neighbour, level+1)) \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        \n",
    "        wordDict = {}\n",
    "        edge = defaultdict(list)\n",
    "        wordId = 0\n",
    "\n",
    "        def addWord(x):\n",
    "            if x not in wordDict:\n",
    "                nonlocal wordId\n",
    "                wordDict[x] = wordId\n",
    "                wordId += 1\n",
    "        \n",
    "        def addEdge(x):\n",
    "            addWord(x)\n",
    "            for i, ch in enumerate(x):\n",
    "                t = x[:i] + '*' + x[i+1:]\n",
    "                addWord(t)\n",
    "                edge[wordDict[x]].append(t)\n",
    "                edge[wordDict[t]].append(x)\n",
    "        \n",
    "        visited = set()\n",
    "        addEdge(beginWord)\n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        queue = deque([(beginWord, 0)])\n",
    "        while queue:\n",
    "            cur, step = queue.popleft()\n",
    "            visited.add(cur)\n",
    "            for bridge in edge[wordDict[cur]]:\n",
    "                if bridge in visited:\n",
    "                    continue\n",
    "                for word in edge[wordDict[bridge]]:\n",
    "                    if word == endWord and word not in visited:\n",
    "                        return step + 2\n",
    "                    queue.append((word, step + 1))\n",
    "                    visited.add(word)\n",
    "                visited.add(bridge)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        queue = [beginWord]\n",
    "        visited = set()\n",
    "        cnt = 1\n",
    "        mapper = collections.defaultdict(list)\n",
    "        for word in wordList:\n",
    "            for i in range(len(beginWord)):\n",
    "                mapper[word[:i] + '*' + word[i+1:]].append(word)\n",
    "            \n",
    "        while len(queue):\n",
    "            for i in range(len(queue)):\n",
    "                cur = queue.pop(0)\n",
    "                if cur in visited:\n",
    "                    continue\n",
    "                if cur == endWord:\n",
    "                    return cnt\n",
    "                \n",
    "                visited.add(cur)\n",
    "                for i in range(len(beginWord)):\n",
    "                    option_states = mapper[cur[:i] + '*' + cur[i+1:]]\n",
    "                    for state in option_states:\n",
    "                        queue.append(state)\n",
    "            cnt += 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # beginword不在wordlist里，但endword要在\n",
    "        if beginWord not in wordList:\n",
    "            wordList.append(beginWord)\n",
    "        word2id, graph = build_graph(wordList)\n",
    "        if endWord not in word2id:\n",
    "            return 0\n",
    "\n",
    "        # 双向BFS\n",
    "        visisted = set()\n",
    "        begin_id, end_id = word2id[beginWord], word2id[endWord]\n",
    "        q1, q2 = set(), set()  # 哈希表表示队列\n",
    "        q1.add(begin_id)\n",
    "        q2.add(end_id)\n",
    "        dist = 0\n",
    "\n",
    "        while len(q1) != 0 and len(q2) != 0:\n",
    "            temp = set()  # 下一轮bfs的队列\n",
    "            # 找到q1中节点的相邻节点\n",
    "            for key in q1:\n",
    "                if key in q2:\n",
    "                    # 该节点出现于同一层，说明双向搜索到相同层\n",
    "                    return dist + 1 # 路径长度+1， 包含起始和终止单词\n",
    "\n",
    "                visisted.add(key)\n",
    "\n",
    "                # 插入所有未访问的邻接节点\n",
    "                for neighbor_id in graph[key]:\n",
    "                    if neighbor_id not in visisted:\n",
    "                        temp.add(neighbor_id)\n",
    "            \n",
    "            dist += 1  # 每扩散一次，路径长度增加\n",
    "            q1, q2 = q2, temp # 轮流扩散\n",
    "        \n",
    "        return 0\n",
    "\n",
    "\n",
    "\n",
    "def build_graph(wordList):\n",
    "    mapping = {}  # 字符串 -> 相邻字符串id\n",
    "    word2id = {}\n",
    "    graph = [[] for _ in range(len(wordList))] # 邻接表\n",
    "    for wid, word in enumerate(wordList):\n",
    "        word2id[word] = wid\n",
    "        # 对每个字符遍历其中间串，并找到与中间串相邻的节点，中间串中一个一个字符为*\n",
    "        \n",
    "        for i, ch in enumerate(word):\n",
    "            temp = word[:i] +'*'+ word[i+1:]\n",
    "            if temp not in mapping:\n",
    "                # 中间字符串不存在\n",
    "                mapping[temp] = [wid]\n",
    "            else:\n",
    "                # 中间字符串存在，在邻接表中建立连接\n",
    "                for neighbor_id in mapping[temp]:\n",
    "                    graph[wid].append(neighbor_id)\n",
    "                    graph[neighbor_id].append(wid)\n",
    "                mapping[temp].append(wid) # 添加到字典中\n",
    "    \n",
    "    return word2id, graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        worddict = defaultdict(list) \n",
    "\n",
    "\n",
    "        for i in range(len(wordList)):\n",
    "            w = wordList[i]\n",
    "            for j in range(len(w)):\n",
    "                nw = w[:j] + '-' + w[j+1:] \n",
    "                worddict[nw].append(w) \n",
    "        \n",
    "        que = [(beginWord,1)]\n",
    "        visited = set()  \n",
    "\n",
    "        while que: \n",
    "            w,size = que.pop(0)\n",
    "            if w in visited:continue   \n",
    "            visited.add(w)\n",
    "            if w == endWord:\n",
    "                return size\n",
    "            for i in range(len(w)):\n",
    "                tmp = w[:i] + '-' + w[i+1:]\n",
    "                for neg in worddict[tmp]:\n",
    "                    que.append((neg,size+1))\n",
    "        \n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def add_children(src_word, step, queue, visited):\n",
    "            nonlocal dummy_word2word, word2dummy_word\n",
    "            dummy_words = word2dummy_word[src_word]\n",
    "            for dummy_word in dummy_words:\n",
    "                for dst_word in dummy_word2word[dummy_word]:\n",
    "                    if dst_word not in visited:\n",
    "                        visited.add(dst_word)\n",
    "                        queue.append((dst_word, step + 1))\n",
    "\n",
    "        dummy_word2word = {}\n",
    "        word2dummy_word = {}\n",
    "        wordList.append(beginWord)\n",
    "        for word in wordList:\n",
    "            word2dummy_word[word] = []\n",
    "            splited_word = [c for c in word]\n",
    "            for i in range(len(word)):\n",
    "                tmp, splited_word[i] = splited_word[i], '*'\n",
    "                dummy_word = ''.join(splited_word)\n",
    "                splited_word[i] = tmp\n",
    "                word2dummy_word[word].append(dummy_word)\n",
    "                if dummy_word not in dummy_word2word:\n",
    "                    dummy_word2word[dummy_word] = []\n",
    "                dummy_word2word[dummy_word].append(word)\n",
    "\n",
    "        queue = deque()\n",
    "        visited = {beginWord}\n",
    "        queue.append((beginWord, 1))\n",
    "        while queue:\n",
    "            word, step = queue.popleft()\n",
    "            if word == endWord:\n",
    "                return step\n",
    "            add_children(word, step, queue, visited)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Vertex:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.color = \"white\"\n",
    "        self.distance = 0\n",
    "        self.neighbor = []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:\n",
    "\n",
    "        VertexQ = dict()\n",
    "        d = {}\n",
    "        wordList.append(beginWord)\n",
    "        for i in wordList:\n",
    "            VertexQ[i] = Vertex(i)\n",
    "        startVertex = Vertex(beginWord)\n",
    "        VertexQ[beginWord] = startVertex\n",
    "\n",
    "        for i in wordList:\n",
    "            for j in range(len(i)):\n",
    "                bucket = i[:j]+\"_\"+i[j+1:]\n",
    "                if bucket in d:\n",
    "                    d[bucket].append(i)\n",
    "                else:\n",
    "                    d[bucket] = [i]\n",
    "        for bucket in d.keys():\n",
    "            for i in d[bucket]:\n",
    "                for j in d[bucket]:\n",
    "                    if i != j:\n",
    "                        VertexQ[i].neighbor.append(VertexQ[j])\n",
    "        def bfs(startV):\n",
    "            startV.distance = 1\n",
    "            VertQ = [startV]\n",
    "            while len(VertQ) > 0:\n",
    "                currentVert = VertQ.pop(0)\n",
    "                temp_distance = currentVert.distance\n",
    "                for nbr in currentVert.neighbor:\n",
    "                    if nbr.color == \"white\":\n",
    "                        nbr.color = \"gray\"\n",
    "                        nbr.distance = temp_distance + 1\n",
    "                        if nbr.val == endWord:\n",
    "                            return nbr.distance\n",
    "                        VertQ.append(nbr)\n",
    "            return 0\n",
    "        return bfs(startVertex)\n",
    "S =Solution()\n",
    "print(S.ladderLength(\"hit\", \"cog\", wordList = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "\n",
    "        # hash_table = {}\n",
    "        # index = 1 \n",
    "        # hash_table[beginWord] = index\n",
    "        # edge_dict = collections.defaultdict(set)\n",
    "\n",
    "        # for i in range(len(beginWord)):\n",
    "        #     target_word = beginWord[0:i] + '_' + beginWord[i+1:]\n",
    "        #     if target_word not in hash_table:\n",
    "        #         index += 1\n",
    "        #         hash_table[target_word] = index\n",
    "\n",
    "        #     edge_dict.get(1,{}).update(hash_table[target_word])\n",
    "        #     edge_dict.get(hash_table[target_word],{}).update(1)\n",
    "\n",
    "        if endWord not in wordList:return 0 \n",
    "        if beginWord not in wordList:wordList.append(beginWord)\n",
    "        index = 0\n",
    "        hash_table = {}\n",
    "        edge_dict = collections.defaultdict(set)\n",
    "        for current_word in wordList:\n",
    "            hash_table[current_word] = index\n",
    "            index+=1\n",
    "            for pos in range(len(current_word)):\n",
    "                target_word = current_word[0:pos] + \"_\" + current_word[pos+1:]\n",
    "                if target_word not in hash_table:\n",
    "                    hash_table[target_word] = index\n",
    "                    index +=1\n",
    "                edge_dict[hash_table[current_word]].add(hash_table[target_word])\n",
    "                edge_dict[hash_table[target_word]].add(hash_table[current_word])\n",
    "\n",
    "        # for key,value in edge_dict.items():\n",
    "        #     print(key,value)\n",
    "        # print(hash_table)\n",
    "\n",
    "        cc_map = collections.defaultdict(int)\n",
    "        cc_map[hash_table[beginWord]] = 1 \n",
    "        cur_iter = [hash_table[beginWord]]\n",
    "        target_index = hash_table[endWord]\n",
    "\n",
    "        while(cur_iter):\n",
    "            next_iter = []\n",
    "            raw_data = set()\n",
    "            this_height = cc_map[cur_iter[0]]\n",
    "            for cur_index in cur_iter:\n",
    "                raw_data.update(edge_dict[cur_index])\n",
    "            # print(raw_data)\n",
    "            for next_index in raw_data:\n",
    "                if next_index == target_index:\n",
    "                    return this_height//2 + 1\n",
    "                if cc_map.get(next_index,10000) >= this_height+1:\n",
    "                    cc_map[next_index] = this_height + 1 \n",
    "                    next_iter.append(next_index)\n",
    "            cur_iter = next_iter\n",
    "        return 0 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        # 构造虚拟节点减少运行时间\n",
    "        word_id_map = dict()\n",
    "        link_map = defaultdict(set)\n",
    "        word_idx = 0\n",
    "\n",
    "        def add_word(word):\n",
    "            if word not in word_id_map:\n",
    "                nonlocal word_idx\n",
    "                word_id_map[word] = word_idx\n",
    "                word_idx += 1\n",
    "\n",
    "        def add_link(word):\n",
    "            add_word(word)\n",
    "            ori_idx = word_id_map[word]\n",
    "            for i in range(len(word)):\n",
    "                c_list = list(word)\n",
    "                c_list[i] = '*'\n",
    "                near_word = ''.join(c_list)\n",
    "                add_word(near_word)\n",
    "                near_word_idx = word_id_map[near_word]\n",
    "                link_map[ori_idx].add(near_word_idx)\n",
    "                link_map[near_word_idx].add(ori_idx)\n",
    "\n",
    "        add_link(beginWord)\n",
    "        for w in wordList:\n",
    "            add_link(w)\n",
    "\n",
    "        queue = deque()\n",
    "        dis = defaultdict(int)\n",
    "        begin_id = word_id_map[beginWord]\n",
    "        end_id = word_id_map[endWord]\n",
    "        queue.append(begin_id)\n",
    "        dis[begin_id] = 1\n",
    "\n",
    "        while queue:\n",
    "            cur_word_id = queue.popleft()\n",
    "            for next_word_id in link_map[cur_word_id]:\n",
    "                if dis[next_word_id] != 0:\n",
    "                    continue\n",
    "                dis[next_word_id] = dis[cur_word_id] + 1\n",
    "                if next_word_id == end_id:\n",
    "                    return dis[next_word_id] // 2 + 1\n",
    "                queue.append(next_word_id)\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, begin: str, end: str, wordList: List[str]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        for word in wordList:\n",
    "            for i in range(len(word)):\n",
    "                vir = word[:i] + '*' + word[i + 1:]\n",
    "                graph[word].append(vir)\n",
    "                graph[vir].append(word)\n",
    "\n",
    "        if end not in graph:\n",
    "            return 0\n",
    "\n",
    "        graph[begin].extend(begin[:i] + '*' + begin[i + 1:] for i in range(len(begin)))\n",
    "        vis_left, vis_right = {begin}, {end}\n",
    "        que_left, que_right = [begin], [end]\n",
    "        dis = 0\n",
    "\n",
    "        while que_left and que_right:\n",
    "            dis += 2\n",
    "\n",
    "            t, que_left = que_left, []\n",
    "            for u in t:\n",
    "                for v in graph[u]:\n",
    "                    if v not in vis_left:\n",
    "                        que_left.append(v)\n",
    "                        vis_left.add(v)\n",
    "\n",
    "            t, que_right = que_right, []\n",
    "            for u in t:\n",
    "                for v in graph[u]:\n",
    "                    if v in vis_left:\n",
    "                        return dis // 2 + 1\n",
    "                    if v not in vis_right:\n",
    "                        que_right.append(v)\n",
    "                        vis_right.add(v)\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        \n",
    "        wordList.append(beginWord)\n",
    "        d = defaultdict(list)\n",
    "        \n",
    "        for w in wordList:\n",
    "            for i, c in enumerate(w):\n",
    "                k = f'{w[:i]}_{w[i+1:]}'\n",
    "                d[k].append(w)\n",
    "        \n",
    "        m = defaultdict(set)\n",
    "        for _, l in d.items():\n",
    "            for w in l:\n",
    "                m[w].update(l)\n",
    "        \n",
    "        #print(m)\n",
    "        \n",
    "        cur = [beginWord]\n",
    "        \n",
    "        visited = set(cur)\n",
    "        step = 1\n",
    "        while cur:\n",
    "            \n",
    "            #print(cur)\n",
    "            next = set()\n",
    "            for w in cur:\n",
    "                 for n in m[w]:\n",
    "                        if n == endWord:\n",
    "                            return step + 1\n",
    "                        \n",
    "                        if n not in visited:\n",
    "                            visited.add(n)\n",
    "                            next.add(n)\n",
    "            cur = next\n",
    "            step += 1\n",
    "        \n",
    "        return 0\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        l = len(beginWord)\n",
    "        if beginWord == endWord:\n",
    "            return 2\n",
    "        wordMap = {}\n",
    "        for word in wordList:\n",
    "            for i in range(0, l):\n",
    "                key = (word[:i], word[i+1:])\n",
    "                if key not in wordMap:\n",
    "                    wordMap[key] = []\n",
    "                wordMap[key].append(word)\n",
    "        words = set(wordList)\n",
    "        cand = set([beginWord])\n",
    "\n",
    "        n = 1\n",
    "        while cand:\n",
    "            # print(cand)\n",
    "            n+=1\n",
    "            new_cand = set()\n",
    "            for word in cand:\n",
    "                for i in range(0, l):\n",
    "                    key = (word[:i], word[i+1:])\n",
    "                    for w in wordMap.get(key, ()):\n",
    "                        # print(w)\n",
    "                        if w == endWord:\n",
    "                            return n\n",
    "                        if w in words:\n",
    "                            words.remove(w)\n",
    "                            new_cand.add(w)\n",
    "            cand = new_cand\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        size = len(beginWord)\n",
    "        choose_dict = defaultdict(list)\n",
    "        visited = defaultdict(bool)\n",
    "\n",
    "        for word in wordList:\n",
    "            for i in range(size):\n",
    "                choose_dict[word[0:i] + '*' + word[i + 1:]].append(word)\n",
    "\n",
    "        def dfs(cur_word, pre_cnt):\n",
    "            if cur_word == endWord:\n",
    "                return pre_cnt\n",
    "\n",
    "            min_cnt = inf\n",
    "            for i in range(size):\n",
    "                next_words = choose_dict[cur_word[0:i] + '*' + cur_word[i + 1:]]\n",
    "                for next_word in next_words:\n",
    "                    if visited[next_word] == False:\n",
    "                        visited[next_word] = True\n",
    "                        min_cnt = min(min_cnt, dfs(next_word, pre_cnt + 1))\n",
    "                        visited[next_word] = False\n",
    "            \n",
    "            return min_cnt\n",
    "\n",
    "        def bfs():\n",
    "            q = deque()\n",
    "            q.append(beginWord)\n",
    "            visited = defaultdict(bool)\n",
    "            visited[beginWord] = True\n",
    "            layer = 0\n",
    "            while q:\n",
    "                layer += 1\n",
    "                q_len = len(q)\n",
    "                for i in range(q_len):\n",
    "                    cur_node = q.popleft()\n",
    "                    print(cur_node)\n",
    "                    if cur_node == endWord:\n",
    "                        return layer\n",
    "                    for j in range(size):\n",
    "                        next_words = choose_dict[cur_node[0:j] + '*' + cur_node[j + 1:]]\n",
    "                        print(next_words)\n",
    "                        for next_word in next_words:\n",
    "                            if not visited[next_word]:\n",
    "                                visited[next_word] = True\n",
    "                                q.append(next_word)\n",
    "            return inf\n",
    "\n",
    "                         \n",
    "                        \n",
    "\n",
    "\n",
    "        \n",
    "        res = bfs()\n",
    "        return res if res != inf else 0\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # 画邻接表\n",
    "        graph = defaultdict(list)\n",
    "        wordList.append(beginWord) # 添加begin\n",
    "        # wordList.append(endWord) # 添加end\n",
    "        wordSet = set(wordList) # 使用set()，避免重复添加\n",
    "        l = len(beginWord)\n",
    "        for i in wordSet:\n",
    "            for j in range(l):\n",
    "                vir_word = i[0:j] + \"*\" + i[j+1:l] # 邻接图内的实节点只连接虚节点\n",
    "                graph[i].append(vir_word) # 实节点只指向虚节点\n",
    "                graph[vir_word].append(i) # 虚节点只指向实节点\n",
    "\n",
    "        # print(graph)\n",
    "        # return 0\n",
    "\n",
    "\n",
    "        if not graph[endWord]: # 终点没有连接任何节点就返回0\n",
    "            return 0\n",
    "\n",
    "        # 这里使用广度优先搜素，记录路径长度\n",
    "        cur_nodes = [beginWord] # 记录目前扩散到的系欸但\n",
    "        visited = set() # 记录访问过的节点\n",
    "        visited.add(beginWord)\n",
    "        length = {beginWord:1} # 记录出发点到访问过的节点的路径长\n",
    "        print(visited)\n",
    "        cur = beginWord\n",
    "        while cur != endWord and cur_nodes:\n",
    "            cur = cur_nodes.pop(0) # 删除并记录正在访问的节点\n",
    "            for i in graph[cur]: # i是虚结点              \n",
    "                for k in graph[i]: # 虚结点连接的实节点\n",
    "                    if k not in visited: # 如果没有访问\n",
    "                        length[k] = length[cur] + 1 # 扩散距离+1\n",
    "                        cur_nodes.append(k) # 进栈\n",
    "                        visited.add(k) # 标记已访问\n",
    "        \n",
    "        if endWord in length:\n",
    "            print(length)\n",
    "            return length[endWord]\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        connections = {}\n",
    "        for word in wordList:\n",
    "            newWord = []\n",
    "            for letter in word:\n",
    "                newWord.append(letter)\n",
    "            for idx in range(len(newWord)):\n",
    "                curLetter = newWord[idx]\n",
    "                newWord[idx] = '*'\n",
    "                tmpWord = ''.join(newWord)\n",
    "                if tmpWord not in connections:\n",
    "                    connections[tmpWord] = set()\n",
    "                connections[tmpWord].add(word)\n",
    "                newWord[idx] = curLetter\n",
    "\n",
    "        # BFS\n",
    "        tobeVisit = [beginWord]\n",
    "        nextLevel = []\n",
    "        visited = set()\n",
    "        visited.add(beginWord)\n",
    "        curDist = 1\n",
    "        while tobeVisit:\n",
    "            curWord = tobeVisit.pop()\n",
    "            if curWord == endWord:\n",
    "                return curDist\n",
    "            newWord = []\n",
    "            for letter in curWord:\n",
    "                newWord.append(letter)\n",
    "\n",
    "            for idx in range(len(newWord)):\n",
    "                curLetter = newWord[idx]\n",
    "                newWord[idx] = '*'\n",
    "                tmpWord = ''.join(newWord)\n",
    "                newWord[idx] = curLetter\n",
    "                if tmpWord not in connections:\n",
    "                    continue\n",
    "                for neighbor in connections[tmpWord]:\n",
    "                    if neighbor in visited:\n",
    "                        continue\n",
    "                    nextLevel.append(neighbor)\n",
    "                    visited.add(neighbor)\n",
    "            \n",
    "            if not tobeVisit:\n",
    "                curDist += 1\n",
    "                tobeVisit = nextLevel\n",
    "                nextLevel = []\n",
    "        return 0\n",
    "\n",
    "    def connected(self, word1, word2):\n",
    "        if len(word1) != len(word2):\n",
    "            return False\n",
    "        dist = 0\n",
    "        for idx in range(len(word1)):\n",
    "            if word1[idx] != word2[idx]:\n",
    "                dist += 1\n",
    "            if dist > 1:\n",
    "                return False\n",
    "        return True\n",
    "'''\n",
    "BFS\n",
    "build connections for each of two words\n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        connections = {}\n",
    "        for word in wordList:\n",
    "            newWord = []\n",
    "            for letter in word:\n",
    "                newWord.append(letter)\n",
    "            for idx in range(len(newWord)):\n",
    "                curLetter = newWord[idx]\n",
    "                newWord[idx] = '*'\n",
    "                tmpWord = ''.join(newWord)\n",
    "                if tmpWord not in connections:\n",
    "                    connections[tmpWord] = set()\n",
    "                connections[tmpWord].add(word)\n",
    "                newWord[idx] = curLetter\n",
    "\n",
    "        # BFS\n",
    "        tobeVisit = [beginWord]\n",
    "        nextLevel = []\n",
    "        visited = set()\n",
    "        curDist = 1\n",
    "        while tobeVisit:\n",
    "            curWord = tobeVisit.pop()\n",
    "            visited.add(curWord)\n",
    "            if curWord == endWord:\n",
    "                return curDist\n",
    "            newWord = []\n",
    "            for letter in curWord:\n",
    "                newWord.append(letter)\n",
    "\n",
    "            for idx in range(len(newWord)):\n",
    "                curLetter = newWord[idx]\n",
    "                newWord[idx] = '*'\n",
    "                tmpWord = ''.join(newWord)\n",
    "                newWord[idx] = curLetter\n",
    "                if tmpWord not in connections:\n",
    "                    continue\n",
    "                for neighbor in connections[tmpWord]:\n",
    "                    if neighbor in visited:\n",
    "                        continue\n",
    "                    nextLevel.append(neighbor)\n",
    "            \n",
    "            if not tobeVisit:\n",
    "                curDist += 1\n",
    "                tobeVisit = nextLevel\n",
    "                nextLevel = []\n",
    "        return 0\n",
    "\n",
    "    def connected(self, word1, word2):\n",
    "        if len(word1) != len(word2):\n",
    "            return False\n",
    "        dist = 0\n",
    "        for idx in range(len(word1)):\n",
    "            if word1[idx] != word2[idx]:\n",
    "                dist += 1\n",
    "            if dist > 1:\n",
    "                return False\n",
    "        return True\n",
    "'''\n",
    "BFS\n",
    "build connections for each of two words\n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        # n²遍历单词来建立关系，复杂度为n²c²，超时\n",
    "        # def is_link(a, b):\n",
    "        #     not_same_num = 0\n",
    "        #     # a = list(a)\n",
    "        #     # b = list(b)\n",
    "        #     n = len(a)\n",
    "        #     for i in range(n):\n",
    "        #         if a[i] != b[i]:\n",
    "        #             not_same_num += 1\n",
    "        #     if not_same_num == 1:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         return False\n",
    "\n",
    "        # wordList.append(beginWord)\n",
    "        # link_word = {}\n",
    "        # for e in wordList:\n",
    "        #     link_word[e] = []\n",
    "        # n = len(wordList)\n",
    "        # for i in range(n-1):\n",
    "        #     for j in range(i+1, n):\n",
    "        #         if is_link(wordList[i], wordList[j]):\n",
    "        #             link_word[wordList[i]].append(wordList[j])\n",
    "        #             link_word[wordList[j]].append(wordList[i])\n",
    "        # q = []\n",
    "        # q.append((beginWord, 1))\n",
    "        # visited = {beginWord:1}\n",
    "        # while q:\n",
    "        #     node, length = q.pop(0)\n",
    "        #     for neighbor in link_word[node]:\n",
    "        #         if neighbor in visited:\n",
    "        #             continue\n",
    "        #         if neighbor == endWord:\n",
    "        #             return length + 1\n",
    "        #         q.append((neighbor, length+1))\n",
    "        #         visited[neighbor] = 1\n",
    "        # return 0\n",
    "        wordList.append(beginWord)\n",
    "        word_list = {}\n",
    "        for e in wordList:\n",
    "            word_list[e] = 1\n",
    "        link = {}\n",
    "        for e in wordList:\n",
    "            link[e] = []\n",
    "        for word in wordList:\n",
    "            for i in range(len(word)):\n",
    "                chars = list(word)\n",
    "                tmp = chars[i]\n",
    "                chars[i] = '*'\n",
    "                new_word = ''.join(chars)\n",
    "                if new_word not in word_list:\n",
    "                    word_list[new_word] = 1\n",
    "                if new_word not in link:\n",
    "                    link[new_word] = []\n",
    "                link[word].append(new_word)\n",
    "                link[new_word].append(word)\n",
    "        q = []\n",
    "        q.append((beginWord, 0))\n",
    "        visited = {beginWord:1}\n",
    "        while q:\n",
    "            word, edge_num = q.pop(0)\n",
    "            for nei in link[word]:\n",
    "                if nei in visited:\n",
    "                    continue\n",
    "                if nei == endWord:\n",
    "                    return (edge_num+1) // 2 + 1\n",
    "                visited[nei] = 1\n",
    "                q.append((nei, edge_num+1))\n",
    "        return 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "#         def addWord(word: str):\n",
    "#             if word not in wordId:\n",
    "#                 nonlocal nodeNum\n",
    "#                 wordId[word] = nodeNum\n",
    "#                 nodeNum += 1\n",
    "        \n",
    "#         def addEdge(word: str):\n",
    "#             addWord(word)\n",
    "#             id1 = wordId[word]\n",
    "#             chars = list(word)\n",
    "#             for i in range(len(chars)):\n",
    "#                 tmp = chars[i]\n",
    "#                 chars[i] = \"*\"\n",
    "#                 newWord = \"\".join(chars)\n",
    "#                 addWord(newWord)\n",
    "#                 id2 = wordId[newWord]\n",
    "#                 edge[id1].append(id2)\n",
    "#                 edge[id2].append(id1)\n",
    "#                 chars[i] = tmp\n",
    "\n",
    "#         wordId = dict()\n",
    "#         edge = collections.defaultdict(list)\n",
    "#         nodeNum = 0\n",
    "\n",
    "#         for word in wordList:\n",
    "#             addEdge(word)\n",
    "        \n",
    "#         addEdge(beginWord)\n",
    "#         if endWord not in wordId:\n",
    "#             return 0\n",
    "        \n",
    "#         dis = [float(\"inf\")] * nodeNum\n",
    "#         beginId, endId = wordId[beginWord], wordId[endWord]\n",
    "#         dis[beginId] = 0\n",
    "\n",
    "#         que = collections.deque([beginId])\n",
    "#         while que:\n",
    "#             x = que.popleft()\n",
    "#             if x == endId:\n",
    "#                 return dis[endId] // 2 + 1\n",
    "#             for it in edge[x]:\n",
    "#                 if dis[it] == float(\"inf\"):\n",
    "#                     dis[it] = dis[x] + 1\n",
    "#                     que.append(it)\n",
    "        \n",
    "#         return 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        def addWord(word: str):\n",
    "            if word not in wordId:\n",
    "                nonlocal nodeNum\n",
    "                wordId[word] = nodeNum\n",
    "                nodeNum += 1\n",
    "        \n",
    "        def addEdge(word: str):\n",
    "            addWord(word)\n",
    "            id1 = wordId[word]\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = \"*\"\n",
    "                newWord = \"\".join(chars)\n",
    "                addWord(newWord)\n",
    "                id2 = wordId[newWord]\n",
    "                edge[id1].append(id2)\n",
    "                edge[id2].append(id1)\n",
    "                chars[i] = tmp\n",
    "\n",
    "        wordId = dict()\n",
    "        edge = collections.defaultdict(list)\n",
    "        nodeNum = 0\n",
    "\n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        \n",
    "        addEdge(beginWord)\n",
    "        if endWord not in wordId:\n",
    "            return 0\n",
    "        \n",
    "        disBegin = [float(\"inf\")] * nodeNum\n",
    "        beginId = wordId[beginWord]\n",
    "        disBegin[beginId] = 0\n",
    "        queBegin = collections.deque([beginId])\n",
    "\n",
    "        disEnd = [float(\"inf\")] * nodeNum\n",
    "        endId = wordId[endWord]\n",
    "        disEnd[endId] = 0\n",
    "        queEnd = collections.deque([endId])\n",
    "\n",
    "        while queBegin or queEnd:\n",
    "            queBeginSize = len(queBegin)\n",
    "            for _ in range(queBeginSize):\n",
    "                nodeBegin = queBegin.popleft()\n",
    "                if disEnd[nodeBegin] != float(\"inf\"):\n",
    "                    return (disBegin[nodeBegin] + disEnd[nodeBegin]) // 2 + 1\n",
    "                for it in edge[nodeBegin]:\n",
    "                    if disBegin[it] == float(\"inf\"):\n",
    "                        disBegin[it] = disBegin[nodeBegin] + 1\n",
    "                        queBegin.append(it)\n",
    "\n",
    "            queEndSize = len(queEnd)\n",
    "            for _ in range(queEndSize):\n",
    "                nodeEnd = queEnd.popleft()\n",
    "                if disBegin[nodeEnd] != float(\"inf\"):\n",
    "                    return (disBegin[nodeEnd] + disEnd[nodeEnd]) // 2 + 1\n",
    "                for it in edge[nodeEnd]:\n",
    "                    if disEnd[it] == float(\"inf\"):\n",
    "                        disEnd[it] = disEnd[nodeEnd] + 1\n",
    "                        queEnd.append(it)\n",
    "        \n",
    "        return 0\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
